home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / sa / btree < prev    next >
Text File  |  1996-08-30  |  16KB  |  630 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- BTREES, also called (a,b)-trees are gerneralized avl-trees
  3. -- 22.3.1995 Holger Klawitter <holger@math.uni-muenster.de>
  4. -- Defined classes:
  5. --   B_TREE{KEY,ELT}
  6. -- Helper classes:
  7. --   B_TREE{KEY,ELT,NODE}
  8. --   BT_NODE{KEY,ELT}
  9. --   BT_NELEM{KEY,ELT,NODE}
  10. ---------------------------------------------------------------------
  11. class B_TREE{ KEY < $IS_LT{KEY}, ELT }
  12. is
  13.    include B_TREE{KEY,ELT,BT_NODE{KEY,ELT}};
  14. end; -- class B_TREE
  15. ----------------------------------------------------------------------
  16. class B_TREE{ KEY < $IS_LT{KEY}, ELT, NODE < $BT_NODE{KEY,ELT,NODE} }
  17.       < $MAP{ KEY, ELT }
  18. is
  19.    -- B_TREES can be used as an alternative of *MAPs. They are optimized
  20.    -- for usage in environment with slow access to elt.
  21.    private include COMPARE{ELT};
  22.    
  23.    private attr root: NODE;
  24.  
  25.    readonly attr size: INT;
  26.    
  27.    create: SAME is return new end;
  28.    
  29.    aset( k: KEY, d: ELT )
  30.    -- Associate d with k and store it in the btree.
  31.    -- If this key already exists in the btree the data will
  32.    -- be overwritten. Association void to the key is
  33.    -- equivalent to delete the key with its data.
  34.       pre ~void(self)
  35.    is
  36.       node,e: NODE;
  37.       pos: INT;
  38.       found: BOOL;
  39.       
  40.       stack ::= #A_STACK{TUP{INT,NODE}};
  41.       item ::= #TUP{KEY,ELT}( k, d );
  42.       if void(root) then
  43.      root := #NODE(item);
  44.      size := 1;
  45.      return
  46.       end;
  47.       
  48.       found := root.find( k, stack );
  49.       node := stack.top.t2;
  50.       pos := stack.pop.t1;
  51.       if found then
  52.      node.setItem( pos, item )
  53.       else
  54.      size := size + 1;
  55.      e := #NODE( item );
  56.      loop
  57.         if node.size < node.maxSize then
  58.            node.nodeInsert( e, pos );
  59.            break!
  60.         elsif node = root then
  61.            root := node.split( e, pos );
  62.            break!
  63.         elsif node.rightFree( stack ) then
  64.            node.pushRight( e, pos, stack );
  65.            break!
  66.         elsif node.leftFree( stack ) then
  67.            node.pushLeft( e, pos, stack );
  68.            break!
  69.         end;
  70.         e := node.split( e, pos );
  71.         node := stack.top.t2;
  72.         pos := stack.pop.t1
  73.      end
  74.       end
  75.    end; -- aset
  76.  
  77.    aget( k: KEY ): ELT
  78.      pre ~void(self)
  79.    is
  80.       stack ::= #A_STACK{TUP{INT,NODE}};
  81.       if root.find(k,stack) then
  82.      return stack.top.t2[stack.top.t1].item.t2;
  83.       else
  84.      return void
  85.       end;
  86.    end; -- aget
  87.    
  88.    delete( k: KEY )
  89.    -- Remove the key and its associated elt from the btree.
  90.       pre ~void(self)
  91.    is
  92.       dummy ::= delete(k)
  93.    end;
  94.    
  95.    delete( k: KEY ): ELT
  96.    -- Removes the key and its associated elt from the btree.
  97.    -- Returns the element being deleted or void if none found.
  98.       pre ~void(self)
  99.    is
  100.       node,delNode: NODE;
  101.       pos, delPos: INT;
  102.       found: BOOL;
  103.  
  104.       if void(root) then return void end;
  105.       stack ::= #A_STACK{TUP{INT,NODE}};
  106.       found := root.find( k, stack );
  107.       if ~found then return void end;
  108.  
  109.       size := size - 1;
  110.       delNode := stack.top.t2;
  111.       delPos := stack.top.t1;
  112.       res ::= delNode[delPos].item.t2;
  113.       
  114.       if ~void(delNode[delPos].node) then -- not a true leaf
  115.      delNode.findPred( stack );
  116.      node := stack.top.t2;
  117.      pos := stack.pop.t1 - 1;
  118.      delNode.setItem( delPos, node[pos].item )
  119.       else
  120.      node := delNode;
  121.      pos := stack.pop.t1
  122.      -- same as delPos, but I want to pop the stack
  123.       end;
  124.       loop
  125.      if node = root then
  126.         node.nodeDelete(pos);
  127.         if node.size = 0 then
  128.            root := node[0].node
  129.         end;
  130.         break!
  131.      elsif node.size > node.minSize then
  132.         node.nodeDelete( pos );
  133.         break!
  134.      elsif node.leftSpare( stack ) then
  135.         node.pullLeft( pos, stack );
  136.         break!
  137.      elsif node.rightSpare( stack ) then
  138.         node.pullRight( pos, stack );
  139.         break!
  140.      end;
  141.      if stack.top.t1 < stack.top.t2.size then
  142.         node.joinRight( pos, stack )
  143.      else
  144.         node.joinLeft( pos, stack )
  145.      end;
  146.      node := stack.top.t2;
  147.      pos := stack.pop.t1
  148.       end;
  149.       return res
  150.    end; -- delete
  151.  
  152.    has_ind( k: KEY ): BOOL
  153.    -- Answer 'true' if such a key exists within the btree.
  154.       pre ~void(self)
  155.    is
  156.       if void(root) then return false end;
  157.       stack ::= #A_STACK{TUP{INT,NODE}};
  158.       res ::= root.find( k, stack );
  159.       return res
  160.    end; -- has_ind
  161.  
  162.    has( e: ELT ): BOOL is return has_elt(e) end;
  163.    
  164.    has_elt( e: ELT ): BOOL
  165.       pre ~void(self)
  166.    is
  167.       loop
  168.      other ::= root.elt!;
  169.      if elt_eq(e,other) then return true end;
  170.       end;
  171.       return false
  172.    end; -- has_elt
  173.  
  174.    str: STR is return SYS::id(self).str end;
  175.    
  176.    copy: SAME
  177.    is
  178.       res ::= #SAME;
  179.       loop
  180.      pair ::= pair!;
  181.      res[pair.t1] := pair.t2
  182.       end;
  183.       return res
  184.    end; -- copy
  185.         
  186.    ind!: KEY
  187.    -- Yield all keys in-order.
  188.       pre ~void(self)
  189.    is
  190.       loop yield root.ind! end
  191.    end;
  192.    
  193.    elt!: ELT
  194.    -- Yield all elt in order of the keys.
  195.       pre ~void(self)
  196.    is
  197.       loop yield root.elt! end
  198.    end;
  199.    
  200.    pair!: TUP{KEY,ELT}
  201.    -- Yield all pairs of key and elt in the order of the keys.
  202.       pre ~void(self)
  203.    is
  204.       loop yield root.pair! end
  205.    end;
  206.    
  207. end; -- class B_TREE
  208. ---------------------------------------------------------------------
  209. abstract class $BT_NODE{ KEY < $IS_LT{KEY}, ELT,
  210.              NODE < $BT_NODE{KEY,ELT,NODE} }
  211. is
  212.     create: SAME;
  213.     create(t:TUP{KEY,ELT}): SAME;
  214.     
  215.     is_eq(n:NODE): BOOL;
  216.     aget(i:INT): BT_NELEM{KEY,ELT,NODE};
  217.     size: INT;
  218.     minSize: INT;
  219.     maxSize: INT;
  220.         
  221.     setItem(pos:INT,t:TUP{KEY,ELT});
  222.     setNode(pos:INT,node:NODE);
  223.     
  224.     leftFree(stack:A_STACK{TUP{INT,NODE}}): BOOL;
  225.     rightFree(stack:A_STACK{TUP{INT,NODE}}): BOOL;
  226.     leftSpare(stack:A_STACK{TUP{INT,NODE}}): BOOL;
  227.     rightSpare(stack:A_STACK{TUP{INT,NODE}}): BOOL;
  228.     
  229.     pushLeft(e:NODE,pos:INT,stack:A_STACK{TUP{INT,NODE}});
  230.     pushRight(e:NODE,pos:INT,stack:A_STACK{TUP{INT,NODE}});
  231.     split(e:NODE,pos:INT): NODE;
  232.     nodeInsert(n:NODE,pos:INT);
  233.     
  234.     pullLeft(pos:INT,stack:A_STACK{TUP{INT,NODE}});
  235.     pullRight(pos:INT,stack:A_STACK{TUP{INT,NODE}});
  236.     joinLeft(pos:INT,stack:A_STACK{TUP{INT,NODE}});
  237.     joinRight(pos:INT,stack:A_STACK{TUP{INT,NODE}});
  238.     nodeDelete(pos:INT);
  239.     
  240.     findPred(stack:A_STACK{TUP{INT,NODE}});
  241.     find(k:KEY,stack:A_STACK{TUP{INT,NODE}}): BOOL;
  242.     
  243.     ind!: KEY;
  244.     elt!: ELT;
  245.     pair!: TUP{KEY,ELT};
  246.     
  247. end;
  248. ----------------------------------------------------------------------
  249. class BT_NODE{ KEY < $IS_LT{KEY}, ELT } < $BT_NODE{KEY,ELT,BT_NODE{KEY,ELT}}
  250. is
  251.    -- This class is inernally used by B_TREE.
  252.    -- It represents the root and all nodes in a B_BTEE.
  253.    -- The general structure of a BT_NODE is as follows:
  254.    -- [0].node [0].item [1].node [1].item ... [k].node [k].item [k+1].node
  255.    -- ([k+1].item is always unused)
  256.    
  257.       --include COMPARABLE;
  258.     include AREF{BT_NELEM{KEY,ELT,SAME}} aset->private aset;
  259.     -- Array of items and nodes.
  260.    
  261.     attr size: INT;
  262.    -- Current fill ratio of the node.
  263.    
  264.    const maxSize: INT := 4;
  265.    -- maximal number of elt tuples.
  266.    -- MUST BE EVEN AND GREATER THAN 2.
  267.    
  268.    const minSize: INT := maxSize / 2;
  269.    
  270.    create: SAME is return new(maxSize+1); end;
  271.    
  272.    create( t: TUP{KEY,ELT} ): SAME
  273.    is
  274.       res ::= new(maxSize+1);
  275.       res.setItem( 0, t );
  276.       res.size := 1;
  277.       return res
  278.    end; -- create
  279.    
  280.    is_eq( n: SAME ): BOOL is return SYS::ob_eq(self,n) end;
  281.    
  282.    setItem( pos: INT, t: TUP{KEY,ELT} )
  283.       pre pos>=0 and pos<=maxSize
  284.    is
  285.       [pos] := [pos].item(t)
  286.    end; -- setItem
  287.    
  288.    setNode( pos: INT, node: SAME )
  289.       pre pos>=0 and pos<=maxSize
  290.    is
  291.       [pos] := [pos].node(node)
  292.    end; -- setNode
  293.  
  294.    -- Predicates for sibling nodes
  295.    
  296.    leftFree( stack: A_STACK{TUP{INT,SAME}} ): BOOL
  297.       pre ~void(stack.top) and stack.top.t2 /= self
  298.    is
  299.       parent ::= stack.top;
  300.       return parent.t1 > 0
  301.         and parent.t2[parent.t1-1].node.size < maxSize
  302.    end; -- leftFree
  303.    
  304.    rightFree( stack: A_STACK{TUP{INT,SAME}} ): BOOL
  305.       pre ~void(stack.top) and stack.top.t2 /= self
  306.    is
  307.       parent ::= stack.top;
  308.       return parent.t1 < parent.t2.size
  309.         and parent.t2[parent.t1+1].node.size < maxSize
  310.    end; -- rightFree
  311.    
  312.    leftSpare( stack: A_STACK{TUP{INT,SAME}} ): BOOL
  313.       pre ~void(stack.top) and stack.top.t2 /= self
  314.    is
  315.       parent ::= stack.top;
  316.       return parent.t1 > 0
  317.         and parent.t2[parent.t1-1].node.size > minSize
  318.    end; -- leftSpare
  319.    
  320.    rightSpare( stack: A_STACK{TUP{INT,SAME}} ): BOOL
  321.       pre ~void(stack.top) and stack.top.t2 /= self
  322.    is
  323.       parent ::= stack.top;
  324.       return parent.t1 < parent.t2.size
  325.         and parent.t2[parent.t1+1].node.size > minSize
  326.    end; -- rightSpare
  327.  
  328.    ------------ Insertion
  329.    
  330.    pushLeft( e: SAME, pos: INT, stack: A_STACK{TUP{INT,SAME}} )
  331.       pre size=maxSize
  332.    is
  333.       parent, left: SAME;
  334.       i, ppos: INT;
  335.       parent := stack.top.t2;
  336.       ppos := stack.top.t1;
  337.       left := parent[ppos-1].node;
  338.       
  339.       left.setItem( left.size, parent[ppos-1].item );
  340.       if pos = 0 then -- item goes up
  341.      left.setNode( left.size+1, e[0].node );
  342.      parent.setItem( ppos-1, e[0].item );
  343.      setNode( 0, e[1].node )
  344.       else -- item[0] goes up, insert item
  345.      parent.setItem( ppos-1, [0].item );
  346.      left.setNode( left.size+1, [0].node );
  347.      loop i:= 0.upto!(pos-2);
  348.         [i] := [i+1]
  349.      end;
  350.      [pos-1] := e[0];
  351.      setNode( pos, e[1].node )
  352.       end;
  353.       left.size := left.size + 1
  354.    end;
  355.    
  356.    pushRight( e: SAME, pos: INT, stack: A_STACK{TUP{INT,SAME}} )
  357.       pre size = maxSize
  358.    is
  359.       parent, right: SAME;
  360.       i, ppos: INT;
  361.       parent := stack.top.t2;
  362.       ppos := stack.top.t1;
  363.       right := parent[ppos+1].node;
  364.       
  365.       loop i:= right.size.downto!( 0 ); -- create some space
  366.      right[i+1] := right[i]
  367.       end;
  368.       right.setItem( 0, parent[ppos].item );
  369.       if pos = size then -- item goes up
  370.      parent.setItem( ppos, e[0].item );
  371.      setNode( size, e[0].node );
  372.      right.setNode( 0, e[1].node )
  373.       else -- last item goes up, item will be inserted.
  374.      parent.setItem( ppos, [size-1].item );
  375.      right.setNode( 0, [size].node );
  376.      setNode( size, [size-1].node );
  377.      loop i := (size-2).downto!(pos);
  378.         [i+1] := [i]
  379.      end;
  380.      [pos] := e[0];
  381.      setNode( pos+1, e[1].node )
  382.       end;
  383.       right.size := right.size + 1
  384.    end;
  385.    
  386.    split( e: SAME, pos: INT ): SAME
  387.       pre size = maxSize
  388.    is
  389.       i: INT;
  390.       newNode: SAME := #;
  391.       if pos <= minSize then -- item does not go right
  392.      loop i := minSize.upto!(size);
  393.         newNode[i-minSize] := [i];
  394.         [i] := void
  395.      end;
  396.      if pos = minSize then -- item goes up
  397.         newNode.setNode( 0, e[1].node );
  398.         setNode( minSize, e[0].node )
  399.      else -- item stays left
  400.         loop i := minSize.downto!(pos+1);
  401.            [i] := [i-1]
  402.         end;
  403.         [pos] := e[0];
  404.         setNode( pos+1, e[1].node );
  405.         e.setItem( 0, [minSize].item );
  406.         setItem( minSize, void )
  407.      end;
  408.       else -- item goes right
  409.      loop i := size.downto!(pos);
  410.         newNode[i-minSize] := [i];
  411.         [i] := void
  412.      end;
  413.      newNode.setNode( pos-minSize, e[1].node );
  414.      newNode[pos-minSize-1] := e[0];
  415.      loop i := (pos-1).downto!(minSize+1);
  416.         newNode[i-minSize-1] := [i];
  417.         [i] := void
  418.      end;
  419.      e.setItem( 0, [minSize].item );
  420.      setItem( minSize, void )
  421.       end;
  422.       size := minSize;
  423.       newNode.size := minSize;
  424.       e.setNode( 0, self ); -- generate the new node to insert.
  425.       e.setNode( 1, newNode );
  426.       assert e.size = 1;
  427.       return e
  428.    end;
  429.    
  430.    nodeInsert( n: SAME, pos: INT )
  431.       pre pos>=0 and pos<=maxSize and size<maxSize
  432.    is
  433.       i: INT;
  434.       loop i := size.downto!(pos);
  435.      [i+1] := [i]
  436.       end;
  437.       [pos] := n[0];
  438.       setNode( pos+1, n[1].node );
  439.       size := size + 1
  440.    end;
  441.    
  442.    ------------ Deletion
  443.    
  444.    pullLeft( pos: INT, stack: A_STACK{TUP{INT,SAME}} )
  445.    is
  446.       parent, left: SAME;
  447.       i, ppos: INT;
  448.       parent := stack.top.t2;
  449.       ppos := stack.top.t1;
  450.       left := parent[ppos-1].node;
  451.       
  452.       loop i := pos.downto!(1); -- Move hole to the left end.
  453.      [i] := [i-1]
  454.       end;
  455.       setItem( 0, parent[ppos-1].item ); -- get from parent
  456.       setNode( 0, left[size].node );
  457.       parent.setItem( ppos-1, left[left.size-1].item ); -- refill parent
  458.       left[left.size] := void;
  459.       left.setItem( left.size-1, void );
  460.       left.size := left.size - 1
  461.    end;
  462.    
  463.    pullRight( pos: INT, stack: A_STACK{TUP{INT,SAME}} )
  464.    is
  465.       parent, right: SAME;
  466.       i, ppos: INT;
  467.       parent := stack.top.t2;
  468.       ppos := stack.top.t1;
  469.       right := parent[ppos+1].node;
  470.       
  471.       loop i := pos.upto!(size-1); -- Close hole.
  472.      [i] := [i+1]
  473.       end;
  474.       setItem( size-1, parent[ppos].item ); -- Get right end from parent.
  475.       setNode( size, right[0].node );
  476.       parent.setItem( ppos, right[0].item );
  477.       loop i := 1.upto!( right.size );
  478.      right[i-1] := right[i]
  479.       end;
  480.       right[right.size] := void; -- more efficient than 'just' setNode.
  481.       right.size := right.size - 1
  482.    end;
  483.    
  484.    joinLeft( pos: INT, stack: A_STACK{TUP{INT,SAME}} )
  485.       pre size = minSize
  486.    is
  487.       parent, left: SAME;
  488.       i, ppos: INT;
  489.       parent := stack.top.t2;
  490.       ppos := stack.top.t1;
  491.       left := parent[ppos-1].node;
  492.       assert left.size = minSize;
  493.       
  494.       loop i := pos.downto!( 1 ); -- Move hole to the left.
  495.      [i] := [i-1]
  496.       end;
  497.       setNode( 0, left[left.size].node ); -- Get from parent.
  498.       setItem( 0, parent[ppos-1].item );
  499.       loop i := size.downto!( 0 ); -- Make BIG hole for left sibling.
  500.      [i+minSize] := [i] -- means [i+left.size] := [i]
  501.       end;
  502.       loop i := 0.upto!(minSize-1);
  503.      [i] := left[i]
  504.       end;
  505.       parent.setNode( ppos-1, self );
  506.       parent.setItem( ppos-1, parent[ppos].item );
  507.       size := maxSize
  508.    end;
  509.    
  510.    joinRight( pos: INT, stack: A_STACK{TUP{INT,SAME}} )
  511.       pre size = minSize
  512.    is
  513.       parent, right: SAME;
  514.       i, ppos: INT;
  515.       parent := stack.top.t2;
  516.       ppos := stack.top.t1;
  517.       right := parent[ppos+1].node;
  518.       assert right.size = minSize;
  519.       
  520.       loop i := (pos+1).upto!( size ); -- Close hole.
  521.      [i-1] := [i]
  522.       end;
  523.       setItem( size-1, parent[ppos].item ); -- Get from parent.
  524.       loop i := 0.upto!( right.size ); -- Do joining.
  525.      [size+i] := right[i]
  526.       end;
  527.       parent.setNode( ppos+1, self );
  528.       size := maxSize
  529.    end;
  530.    
  531.    nodeDelete( pos: INT )
  532.       pre pos>=0 and pos<=maxSize
  533.    is
  534.       i: INT;
  535.       loop i := pos.upto!(size-1);
  536.      [i] := [i+1]
  537.       end;
  538.       [size] := void;
  539.       size := size - 1
  540.    end;
  541.    
  542.    findPred( stack: A_STACK{TUP{INT,SAME}} )
  543.    is
  544.       node ::= stack.top.t2[stack.top.t1].node;
  545.       loop until!( void(node) );
  546.      stack.push( #TUP{INT,SAME}(node.size, node) );
  547.      node := node[node.size].node
  548.       end
  549.    end;
  550.    
  551.    ------------ Retrieval
  552.    
  553.    find( k: KEY, stack: A_STACK{TUP{INT,SAME}} ): BOOL
  554.    is
  555.       if void(self) then return false end;
  556.       loop
  557.      i ::= 0.upto!(size-1);
  558.      if [i].item.t1 = k then
  559.         stack.push( #TUP{INT,SAME}(i,self) );
  560.         return true
  561.      elsif k < [i].item.t1 then
  562.         stack.push( #TUP{INT,SAME}(i,self) );
  563.         return ~void([i].node) and [i].node.find( k, stack )
  564.      end
  565.       end;
  566.       stack.push( #TUP{INT,SAME}(size,self) );
  567.       return ~void([size].node) and [size].node.find( k, stack )
  568.    end;
  569.  
  570.    ------------ Iterators
  571.    
  572.    ind!: KEY
  573.    is
  574.       if ~void(self)
  575.       then
  576.      loop
  577.         i ::= 0.upto!(size);
  578.         loop yield [i].node.ind! end;
  579.         if ~void([i].item) -- and i<size but this is redunant
  580.         then yield [i].item.t1
  581.         end
  582.      end
  583.       end
  584.    end;
  585.    
  586.    elt!: ELT
  587.    is
  588.       if ~void(self)
  589.       then
  590.      loop
  591.         i ::= 0.upto!(size);
  592.         loop yield [i].node.elt! end;
  593.         if ~void([i].item) -- and i<size but this is redunant
  594.         then yield [i].item.t2
  595.         end
  596.      end
  597.       end
  598.    end;
  599.    
  600.    pair!: TUP{KEY,ELT}
  601.    is
  602.       if ~void(self)
  603.       then
  604.      loop
  605.         i ::= 0.upto!(size);
  606.         loop yield [i].node.pair! end;
  607.         if ~void([i].item) -- and i<size but this is redunant
  608.         then yield [i].item
  609.         end
  610.      end
  611.       end
  612.    end;
  613.    
  614. end; -- class BT_NODE
  615. ----------------------------------------------------------------------
  616. immutable class BT_NELEM{KEY<$IS_LT{KEY},
  617.              ELT,
  618.              NODE < $BT_NODE{ KEY, ELT, NODE }
  619.              }
  620. -- BT_NELEM is being internally used by BT_NODE to store the
  621. -- nodes and the items efficiently.
  622. is
  623.    attr node: NODE;
  624.    attr item: TUP{ KEY, ELT };
  625.    create( n: NODE, i: TUP{KEY,ELT} ): SAME
  626.    is
  627.       return node(n).item(i)
  628.    end;
  629. end; -- class BT_NELEM
  630.